package com.sympsel.Optimal_Algorithm_OA;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Prefix_Sum {
    public static void prefix_sum2D() {
        Scanner in = new Scanner(System.in);
        int rows = 0, cols = 0, times = 0;
        rows = in.nextInt();
        cols = in.nextInt();
        times = in.nextInt();

        long[][] dp = new long[rows + 1][];
        dp[0] = new long[cols + 1];
        for (int i = 1; i < rows + 1; i++) {
            dp[i] = new long[cols + 1];
            for (int j = 1; j < cols + 1; j++) {
                dp[i][j] = in.nextLong() - dp[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1];
            }
        }
        while (times-- > 0) {
            int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
            System.out.println(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]);

        }
        in.close();
    }

    private static void test1() {
        prefix_sum2D();
    }

    public static void main(String[] args) {
        test1();
    }

    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        if (dp[n - 1] - nums[0] + nums[n - 1] == 0) {
            return 0;
        }
        for (int i = 1; i < n - 1; i++) {
            if (dp[i] == dp[n - 1] - dp[i + 1] + nums[n - 1]) {
                return i;
            }
        }

        if (dp[n - 1] == 0) {
            return n - 1;
        }
        return -1;
    }

    @Test
    public void test2() {
        int[][] nums = {
//                {1, 7, 3, 6, 5, 6},
//                {2, 1, -1},
                {-1, -1, -1, -1, -1, 0}
        };
        for (int[] num : nums) {
            System.out.println(pivotIndex(num));
        }
    }

    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, ret = 0;
        for (int x : nums) {
            sum += x;
            int temp = (sum % k + k) % k;
            ret += map.getOrDefault(temp, 0);
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }
        return ret;
    }

    @Test
    public void test3() {
        int[] nums = {4, 5, 0, -2, -3, 1};
        int k = 5;
        System.out.println(subarraysDivByK(nums, k));
    }

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += (nums[i] == 0 ? -1 : 1);
            if (map.containsKey(sum)) {
                ret = Math.max(ret, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return ret;
    }

    @Test
    public void test4() {
        int[] nums = {0, 1, 1, 1, 1, 1, 0, 0, 0};
        System.out.println(findMaxLength(nums));
    }

    public int[][] matrixBlockSum(int[][] mat, int k) {
        int[][] dp = getDP(mat);
        int rows = mat.length, cols = mat[0].length;
        int[][] ret = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int x1 = Math.max(0, i - k);
                int y1 = Math.max(0, j - k);
                int x2 = Math.min(rows - 1, i + k);
                int y2 = Math.min(cols - 1, j + k);
                ret[i][j] = dp[x2][y2];
                boolean a = x1 > 0, b = y1 > 0;

                if (a) {
                    ret[i][j] -= dp[x1 - 1][y2];
                }
                if (b) {
                    ret[i][j] -= dp[x2][y1 - 1];
                }
                if (a && b) {
                    ret[i][j] += dp[x1 - 1][y1 - 1];
                }
            }
        }

        return ret;
    }

    private int[][] getDP(int[][] mat) {
        int rows = mat.length, cols = mat[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = mat[0][0];
        for (int i = 1; i < cols; i++) {
            dp[0][i] = dp[0][i - 1] + mat[0][i];
        }
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + mat[i][0];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j  -1] - dp[i - 1][j - 1] + mat[i][j];
            }
        }
        return dp;
    }

    @Test
    public void test5() {
        int[][] mat = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        System.out.println(Arrays.deepToString(matrixBlockSum(mat, 1)));
    }
}
